The invention relates to improvements of access to data in the general form of TRIE tree indexed records. TRIE tree indexes are described in Knuth: The Art of Computer Programming, "Searching and Sorting" (pp. 481-505) (1973), in Aho, Hopcroft, and Ullman: Data Structures and Algorithms (pp. 163-169)(1983), in Kruse: Data Structures and Program Design (pp. 377-382)(1984), and as radix search trees in Sedgewick: Algorithms (pp. 213-223)(1983).
The use of such a tree for a multi-user database system with enhancements to concurrent access features is described in U.S. Pat. No. 4,914,569 to Levine and Mohan describing a means to traverse a B-Tree or TRIE tree in an orderly fashion while checking and updating the multi-user-access system on a node-by-node basis.
A design to improve query access to records indexed by TRIE trees is described in U.S. Pat. No. 4,774,657 to Anderson et al. describing a means to reduce the number of pages accessed to count the subtree leafs corresponding to a given query.
The quality of access to records can be described in general by the amount of time required to repaint the query screen. In other words, a figure of merit can be based on the perceived delay presented to the user issuing a database query.
Often a broadly stated query to a large database will return far more information than can be displayed simultaneously on a screen. In such circumstances the user is often given a scrollable partial listing of records. In such a user interface only a small subset of the records requested needs to be retrieved for display on the screen along with the record number range and the maximum number of records returned by the query. When the user scrolls to a different part of the listing, only another small subset of the records needs to be retrieved and displayed on the screen.
Typical relational database systems provide this information after building temporary tables which are arrays of records retrieved in record number order. Although such arrays are easy to access by record number, such arrays can be time consuming to build. Often the entire query is executed to build them. This can result in a lengthy delay before any information about the first subset of records and the total number of records can be retrieved for the user.
The quality of access to records can be improved by eliminating the construction of temporary tables, and retrieving the first subset of records and the total number of records via a system of indirect references described in this invention. Other subsets of the records can also be retrieved via the same system of indirect references.
The user can then decide to alter the query slightly to better describe the information sought, without invoking the overhead of fully executing a query.